public class Solution87 {
    int[][][] memo;

    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        memo = new int[n][n][n];
        return dfs(s1, s2, 0, 0, n);
    }

    boolean dfs(String s1, String s2, int i, int j, int len) {
        if (memo[i][j][len - 1] != 0) {
            return memo[i][j][len - 1] == 1;
        }

        if (len == 1) {
            if (s1.charAt(i) == s2.charAt(j)) {
                memo[i][j][len - 1] = 1;
                return true;
            } else {
                memo[i][j][len - 1] = -1;
                return false;
            }
        }

        if (s1.substring(i, i + len).equals(s2.substring(j, j + len))) {
            memo[i][j][len - 1] = 1;
            return true;
        }

        for (int k = 1; k < len; k++) {
            if (dfs(s1, s2, i, j, k) && dfs(s1, s2, i + k, j + k, len - k)) {
                memo[i][j][len - 1] = 1;
                return true;
            }
            if (dfs(s1, s2, i, j + len - k, k) && dfs(s1, s2, i + k, j, len - k)) {
                memo[i][j][len - 1] = 1;
                return true;
            }
        }
        memo[i][j][len - 1] = -1;
        return false;
    }
}
